#include <iostream>
#include <vector>
using namespace std;

int search(vector<int> &nums, int target)
{
    int left = 0, right = nums.size() - 1;
        while(left <= right){
            int mid = (right - left) / 2 + left;
            int num = nums[mid];
            if (num == target) {
                return mid;
            } else if (num > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
}


int main()
{
    vector<int> num = {-1,0,3,5,9,12};
    cout << search(num,9) << endl;
    return 0;
}
